#include "binarytree.h"
#include <iostream>
using namespace std;

BinaryTree::BinaryTree()
{
    m_pRoot = 0;
    m_nodeNum = 0;
}

BinaryTree::~BinaryTree()
{
    clear();
}

void BinaryTree::clear()
{
    remove(m_pRoot);
}

void BinaryTree::remove(ST_NODE*& pNode)
{
    if(!pNode)
        return;

    remove(pNode->pRight);
    remove(pNode->pLeft);

    delete pNode;
    pNode = 0;
    m_nodeNum--;
}


void BinaryTree::traversal(const short &type) const
{
    traversal(m_pRoot, type);
}

void BinaryTree::traversal(const ST_NODE *pNode, const short &type) const
{
    if(!pNode)
    {
        return;
    }

    if(type == 1)
        cout<<pNode->value<<"("<<pNode->count<<"_"<<(pNode->color?"R":"B")<<")"<<' ';
    traversal(pNode->pLeft, type);
    if(type == 0)
        cout<<pNode->value<<"("<<pNode->count<<"_"<<(pNode->color?"R":"B")<<")"<<' ';
    traversal(pNode->pRight, type);
    if(type == -1)
        cout<<pNode->value<<"("<<pNode->count<<"_"<<(pNode->color?"R":"B")<<")"<<' ';
}

bool BinaryTree::empty()
{
    if(m_pRoot)
        return false;
    return true;
}

bool BinaryTree::remove(const int& value)
{
    ST_NODE* pNode = find(value, m_pRoot);
    if(pNode)
    {

        // 同时存在左右子树，调整为单子树类型
        if(pNode->pLeft && pNode->pRight)
        {
            ST_NODE* pNodeMin = findMin(pNode->pRight);
            pNode->value = pNodeMin->value;
            pNode->count = pNodeMin->count;
            pNode = pNodeMin;
        }

        // 删除仅存在单子树结点
        if(pNode->pLeft)
        {
            pNode->value = pNode->pLeft->value;
            pNode->count = pNode->pLeft->count;

            delete pNode->pLeft;
            pNode->pLeft = 0;
        }
        else if(pNode->pRight)
        {
            pNode->value = pNode->pRight->value;
            pNode->count = pNode->pRight->count;

            delete pNode->pRight;
            pNode->pRight = 0;
        }
        // 删除叶子结点
        else
        {
            deleteFixup(pNode);

            if(pNode == m_pRoot)
            {
                m_pRoot = 0;
            }
            else
            {
                if(pNode == pNode->pParent->pLeft)
                    pNode->pParent->pLeft = 0;
                else
                    pNode->pParent->pRight = 0;
            }

            delete pNode;
            pNode = 0;
        }
    }
    else
    {
        return false;
    }

    return true;
}

unsigned int  BinaryTree::find(const int& value)
{
    ST_NODE* pNode = find(value, m_pRoot);
    if(pNode)
        return pNode->count;
    else
        return 0;
}

ST_NODE* BinaryTree::find(const int& value, ST_NODE* pParent)
{
/*
    // 递归实现
    if(!pParent || pParent->value == value)
        return pParent;
    else if(pParent->value > value)
        return find(value, pParent->pLeft);
    else
        return find(value, pParent->pRight);
*/
    // 非递归实现
    while(pParent && pParent->value != value)
    {
        if(pParent->value > value)
            pParent = pParent->pLeft;
        else
            pParent = pParent->pRight;
    }
    return pParent;
}

ST_NODE* BinaryTree::findMin(ST_NODE *pParent) const
{
/*
    // 递归实现
    if(!pParent || !(pParent->pLeft))
        return pParent;
    return findMin(pParent->pLeft);
*/
    // 非递归实现
    if(!pParent)
        return 0;

    ST_NODE* pTempNode = pParent;
    while(pTempNode->pLeft)
    {
        pTempNode = pTempNode->pLeft;
    }
    return pTempNode;

//    ST_NODE** pTempNode = &pParent;
//    while(*pTempNode)
//    {
//        pTempNode = &((*pTempNode)->pLeft);
//    }
//    return *pTempNode;
}

void BinaryTree::rotateLeft(ST_NODE *pNode)
{
    if(!pNode || !(pNode->pRight))
        return;

    ST_NODE* pY = pNode->pRight;
    pNode->pRight = pY->pLeft;

    // 更新父结点
    if(pNode->pRight)
        pNode->pRight->pParent = pNode;
    pY->pParent = pNode->pParent;

    // 当前结点为根结点，更新根结点
    if(!pNode->pParent)
        m_pRoot = pY;
    else
    {
        if(pNode == pNode->pParent->pLeft)
            pNode->pParent->pLeft = pY;
        else
            pNode->pParent->pRight = pY;
    }

    pY->pLeft = pNode;
    pNode->pParent = pY;
}

void BinaryTree::rotateRight(ST_NODE *pNode)
{
    if(!pNode || !(pNode->pLeft))
        return;

    ST_NODE* pY = pNode->pLeft;
    pNode->pLeft = pY->pRight;

    // 更新父结点
    if(pNode->pLeft)
        pNode->pLeft->pParent = pNode;
    pY->pParent = pNode->pParent;

    // 当前结点为根结点，更新根结点
    if(!pNode->pParent)
        m_pRoot = pY;
    else
    {
        if(pNode == pNode->pParent->pLeft)
            pNode->pParent->pLeft = pY;
        else
            pNode->pParent->pRight = pY;
    }

    pY->pRight = pNode;
    pNode->pParent = pY;
}

void BinaryTree::deleteFixup(ST_NODE *pNode)
{
    while(pNode->color == BT_BLACK && pNode->pParent)
    {
        ST_NODE* pParent = pNode->pParent;

        if(pNode == pParent->pLeft)
        {
             ST_NODE* pOther = pParent->pRight;

            // 情形1 兄弟节点为红
            if(pOther->color == BT_RED)
            {
                pParent->color = BT_RED;
                pOther->color = BT_BLACK;
                rotateLeft(pParent);
                pOther = pParent->pRight;
            }

            // 情形2 兄弟为黑，且兄弟的两个孩子也为黑，调整为一红一黑
            if((pOther->pLeft == 0 || pOther->pLeft->color == BT_BLACK)
                    && (pOther->pRight == 0 || pOther->pRight->color == BT_BLACK))
            {

                pOther->color = BT_RED;
                pNode = pParent;
                continue;
            }

            // 情形3 兄弟节点的子结点为右黑左红
            if(pOther->pRight == NULL || pOther->pRight->color == BT_BLACK)
            {
                pOther->pLeft->color = BT_BLACK;
                pOther->color = BT_RED;
                rotateRight(pOther);
                pOther = pParent->pRight;
            }

            // 情形4 兄弟节点的右孩子为红，左孩子不关心
            pOther->pRight->color=BT_BLACK;
            pOther->color = pParent->color;
            pParent->color = BT_BLACK;
            rotateLeft(pParent);

            break;
        }
        else
        {
            ST_NODE* pOther = pParent->pLeft;

            if(pOther->color == BT_RED)
            {
                pParent->color = BT_RED;
                pOther->color = BT_BLACK;
                rotateRight(pParent);
                pOther = pParent->pLeft;
            }

            if( (pOther->pLeft == NULL || pOther->pLeft->color == BT_BLACK)
                    && (pOther->pRight == NULL || pOther->pRight->color == BT_BLACK))
            {
                pOther->color=BT_RED;
                pNode = pParent;
                continue;
            }

            if( pOther->pLeft == NULL || pOther->pLeft->color == BT_BLACK)
            {
                pOther->pRight->color = BT_BLACK;
                pOther->color = BT_RED;
                rotateLeft(pOther);
                pOther = pParent->pLeft;
            }

            pOther->pLeft->color = BT_BLACK;
            pOther->color = pParent->color;
            pParent->color = BT_BLACK;
            rotateRight(pParent);

            break;
        }
    }

    pNode->color = BT_BLACK;
}

void BinaryTree::insertFixup(ST_NODE *pNode)
{
    if(!pNode)
        return;

    ST_NODE* pParent = pNode->pParent;
    ST_NODE* pGParent = 0;

    while((pParent = pNode->pParent) && pParent->color == BT_RED)
    {
        // 红色结点一定存在父结点
        pGParent = pParent->pParent;

        // 父结点为左结点
        if(pParent == pGParent->pLeft)
        {
            ST_NODE* pUncle = pGParent->pRight;
            if(pUncle && pUncle->color == BT_RED)
            {
                pUncle->color = BT_BLACK;
                pParent->color = BT_BLACK;
                pGParent->color = BT_RED;
                pNode = pGParent;
                continue;
            }

            if(pNode == pParent->pRight)
            {
                rotateLeft(pParent);
                pNode = pParent;
                pParent = pNode->pParent;
            }

             pParent->color = BT_BLACK;
             pGParent->color = BT_RED;
             rotateRight(pGParent);
        }
        // 父结点为右结点
        else
        {
            ST_NODE* pUncle = pGParent->pLeft;
            if(pUncle && pUncle->color == BT_RED)
            {
                pUncle->color = BT_BLACK;
                pParent->color = BT_BLACK;
                pGParent->color = BT_RED;
                pNode = pGParent;
                continue;
            }

            if(pNode == pParent->pLeft)
            {
                rotateRight(pParent);
                pNode = pParent;
                pParent = pNode->pParent;
            }

             pParent->color = BT_BLACK;
             pGParent->color = BT_RED;
             rotateLeft(pGParent);
        }
    }

    m_pRoot->color = BT_BLACK;
}

void BinaryTree::insert(const int& value)
{
    // 已存在结点，只增加结点重复计数
    ST_NODE* pNode = find(value, m_pRoot);
    if(pNode)
    {
        (pNode->count)++;
    }
    else
    {
        ST_NODE** pNewNode = &m_pRoot;
        ST_NODE* pParentNode = 0;
        while(*pNewNode)
        {
            pParentNode = *pNewNode;
            if((*pNewNode)->value > value)
                pNewNode = &(*pNewNode)->pLeft;
            else
                pNewNode = &(*pNewNode)->pRight;
        }

        (*pNewNode) = new ST_NODE();
        (*pNewNode)->value = value;
        (*pNewNode)->pLeft = 0;
        (*pNewNode)->pRight = 0;
        (*pNewNode)->count = 1;
        (*pNewNode)->pParent = pParentNode;
        (*pNewNode)->color = BT_RED;
        m_nodeNum++;

        insertFixup(*pNewNode);
    }
}
